package com.demo.java.OD501_550.OD505;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【过滤组合字符串(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146475331
 */
public class OdMain {
    public static ArrayList<String> res_str_list;

    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        String num_str = in.nextLine();  // 输入的数字字符串
        String block_str = in.nextLine();  // 输入的屏蔽字符字符串

        // 预设值：数字到字符的映射
        HashMap<Character, String> num_char_map = new HashMap<Character, String>();

        // 填充数字到字符的映射
        num_char_map.put('0', "abc");
        num_char_map.put('1', "def");
        num_char_map.put('2', "ghi");
        num_char_map.put('3', "jkl");
        num_char_map.put('4', "mno");
        num_char_map.put('5', "pqr");
        num_char_map.put('6', "st");
        num_char_map.put('7', "uv");
        num_char_map.put('8', "wx");
        num_char_map.put('9', "yz");

        res_str_list = new ArrayList<String>();  // 用于存储结果组合
        ArrayList<Character> char_list_temp = new ArrayList<Character>();  // 临时存储字符
        dfs(num_str, char_list_temp, 0, num_char_map);  // 生成所有组合

        int result_count = res_str_list.size();
        String output_str = "";

        // 过滤掉包含屏蔽字符的组合
        for (String x : res_str_list) {
            if (!check(x, block_str)) {
                output_str += x + " ";
            }
        }

        // 输出有效组合
        System.out.println(output_str.substring(0, output_str.length() - 1));
    }

    // 判断组合中是否包含屏蔽字符
    public static boolean check(String string1, String string2) {
        Set<Character> set1 = new HashSet<Character>();
        for (int i = 0; i < string1.length(); i++) {
            set1.add(string1.charAt(i));
        }

        Set<Character> set2 = new HashSet<Character>();
        for (int i = 0; i < string2.length(); i++) {
            set2.add(string2.charAt(i));
        }

        // 检查每个屏蔽字符是否存在于组合中
        for (Character single_char : set2) {
            if (!set1.contains(single_char)) {
                return false;
            }
        }

        return true;
    }

    // 递归生成所有组合
    public static void dfs(String num_str, ArrayList<Character> list, int index, HashMap<Character, String> num_char_map) {
        if (index == num_str.length()) {
            String temp_str = "";
            for (int i = 0; i < list.size(); i++) {
                temp_str = temp_str + list.get(i);
            }
            res_str_list.add(temp_str);  // 将生成的组合加入结果列表
            return;
        }

        // 对当前数字选择对应的所有字符
        for (char single_char : num_char_map.get(num_str.toCharArray()[index]).toCharArray()) {
            list.add(single_char);  // 添加当前字符
            dfs(num_str, list, index + 1, num_char_map);  // 递归处理下一个字符
            list.remove(list.size() - 1);  // 回溯，移除当前字符
        }
    }
}